package leetcode_day._2021._202108._2131;

import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/8/31 19:33
 * 航班预订统计
 * 算法：前缀和  差分数组
 */
public class _31_1109 {
    public static void main(String[] args) {
        //  1    2    3    4    5
        // 10    0   -10   0    0
        // 10   20   -10  -20   0
        // 10   45   -10  -20   0
        // 10   55    45  25    25
        int[][] bookings = {{1, 2, 10}, {2, 3, 20}, {2, 5, 25}};
        int n = 5;
        System.out.println(Arrays.toString(new _31_1109().corpFlightBookings_nn(bookings, n)));
    }

    public int[] corpFlightBookings_nn(int[][] bookings, int n) {
        int[] ans = new int[n];
        for (int[] booking : bookings) {
            for (int i = booking[0]; i <= booking[1]; i++) ans[i - 1] += booking[2];
        }
        return ans;
    }

    public int[] corpFlightBookings(int[][] bookings, int n) {
        // 这里把长度定为 n + 1，少了判断 booking[1] < n
        // tmp[n] 没啥用
        int[] tmp = new int[n + 1];
        for (int[] booking : bookings) {
            tmp[booking[0] - 1] += booking[2];
            tmp[booking[1]] -= booking[2];
        }
        int[] ans = new int[n];
        ans[0] = tmp[0];
        for (int i = 1; i < n; i++) ans[i] = ans[i - 1] + tmp[i];
        return ans;
    }

}
